1837- 二叉树遍历1

这题题目顺序存储方式其实就是层次遍历。
空节点用#来表示，也就是相当于给你一棵完全二叉树。
1.输入方式：

cin>>s;
n = s.size();
s=' ' + s;

2.遍历方式：

• 一种方式，可以写3个遍历。

//先序遍历
void dfs(int i )
{
	if(s[i]=='#') return;
	cout<<s[i];
	if(i*2<=n) dfs(i*2);
	if(i*2+1<=n) dfs(i*2+1);
}

• 偷懒方式，一个递归解决，要判断是哪种遍历

void dfs(int i, int k)
{
	if(s[i]=='#') return;
	if(k==1)cout<<s[i];
	if(i*2<=n) dfs(i*2,k);
	if(k==2)cout<<s[i];
	if(i*2+1<=n) dfs(i*2+1,k);
	if(k==3)cout<<s[i];
}

这样在主程序只要调用$3$次即可。

...
dfs(1,1);
cout<<endl;
dfs(1,2);
cout<<endl;
dfs(1,3);
...